Factorisation de graphes

Une 1-factorisation du graphe de Desargues : chaque classe de couleur est un 1-facteur.

Le graphe de Petersen peut être partitionné en un 1-facteur 1 (en rouge) et un 2-facteur 2 (en bleu). Cependant, le graphe n'est pas 1-factorisable.

En théorie des graphes, un facteur d'un graphe G est un graphe partiel, c'est-à-dire un graphe qui a le même ensemble de sommets que G et dont les arêtes sont contenues dans celles de G. Un k -facteur d'un graphe est un graphe partiel k-régulier, et une k-factorisation partitionne les arêtes du graphe en des k-facteurs disjoints. Un graphe G est dit k-factorisable s'il admet une k-factorisation. En particulier, un 1-facteur est une couplage parfait et une 1-factorisation d'un graphe k-régulier est une coloration des arêtes avec k couleurs. Un 2-facteur est une collection de cycles qui couvre tous les sommets du graphe.

1-factorisation

Un graphe qui est 1-factorisable (c'est-à-dire qui admet une 1-factorisation) est un graphe régulier. La réciproque est fausse : tous les graphes réguliers ne sont pas 1-factorisables. Un graphe k -régulier est 1-factorisable 1 s'il a un indice chromatique égal à k ; des exemples de tels graphes comprennent notamment :

• Tout graphe biparti régulier. Le théorème de mariage de Hall montre en effet qu'un graphe biparti k-régulier contient un couplage parfait. On peut alors supprimer ce couplage parfait et on obtient a graphe biparti ( k − 1)-régulier, auquel on applique le même raisonnement.
• Tout graphe complet avec un nombre pair de nœuds (voir aussi ci-dessous ).

Il existe également des graphes k-réguliers qui ont un indice chromatique k + 1, et ces graphes ne sont pas 1-factorisables ; des exemples de tels graphies sont :

• Tout graphe régulier avec un nombre impair de sommets.
• Le graphe de Petersen .

Graphes complets

Une 1-factorisation de K ₈ ; chaque 1-facteur consiste en une arête du centre à un sommet d'un heptagone avec les trois arêtes parallèles possibles.

Une 1-factorisation d'un graphe complet correspond à des couplage dans un tournoi toutes rondes . La 1-factorisation des graphes complets est un cas particulier d'un théorème de Baranyai (en) concernant la 1-factorisation des hypergraphes complets.

Une méthode de construire d'une 1-factorisation d'un graphe complet avec un nombre pair de sommets consiste à placer tous les sommets sauf un sur un cercle, formant un polygone régulier, avec le sommet restant au centre du cercle. Avec cet arrangement de sommets, on construit un 1-facteur 1 du graphe en choisissant une arête e du centre à un sommet de polygone et on prend de plus les arêtes possibles qui se trouvent sur des droites perpendiculaires à e . Les 1-facteurs construits de cette manière forment une 1-factorisation du graphe.

Le nombre de 1-factorisations distinctes de K ₂, K ₄, K ₆, K ₈, ... est 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, . . .  A000438 .

Conjecture de 1-factorisation

Soit G un graphe k-régulier à 2 n nœuds. On sait que si k est suffisamment grand, G est-factorisable ; c'est le cas notamment :

• Si k = 2 n − 1, alors G est le graphe complet K _{2 n}, et donc 1-factorisable en 1 (voir ci-dessus ).
• Si k = 2 n − 2, alors G peut être construit en supprimant un couplage parfait de K _{2 n} . À nouveau, G est 1-factorisable à 1.
• Chetwynd et Hilton (1985) ont montré que si k ≥ 12n/7, alors G est factorisable en 1.

La conjecture de 1-factorisation affirme que k ≈ n est suffisant au sens suivant :

• Si n est impair et k ≥ n ou si n est pair et k ≥ n − 1, alors G est 1-factorisable.

La conjecture du trop plein (overfull conjecture du graphe trop plein) implique la conjecture de 1-factorisation.

1-factorisation parfaite

Un couple parfait issu d'une 1-factorisation est un couple de 1-facteurs dont l'union induit un cycle hamiltonien .

Une 1-factorisation parfaite d'un graphe est une 1-factorisation ayant la propriété que chaque paire de 1-facteurs est une paire parfaite. Une 1-factorisation 1 parfaite ne doit pas être confondue avec un couplage parfait (également appelé un 1-facteur).

En 1964, Anton Kotzig a conjecturé que tout graphe complet K _{2 n} pour n ≥ 2 possède une 1-factorisation parfaite. Jusqu'à présent, on sait que les graphes suivants possèdent une 1-factorisation parfaite :

• la famille infinie des graphes complets $K_{2p}$, où p est un nombre premier impair (prouvé par Anderson et aussi par Nakamura, indépendamment),
• la famille infinie des graphes complets $K_{p+1}$, où p est un nombre premier impair,
• et on a des résultats supplémentaires épars, y compris $K_{2n}$ où 2n ∈ {16, 28, 36, 40, 50, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792}. Certains résultats plus récents sont rassemblés ici.

Si un graphe complet $K_{n+1}$ a une 1-factorisation parfaite, alors le graphe biparti complet $K_{n,n}$ a aussi une 1-factorisation parfaite.

2-factorisation

Un graphe 2-factorisable doit être 2k -régulier pour un entier k. Julius Petersen a montré en 1891 que cette condition nécessaire est aussi suffisante : tout graphe 2 k -régulier est 2-factorable.

Un graphe connexe 2k -régulier qui a un nombre pair d'arêtes peut être k -factorisé en choisissant pour chacun des deux facteurs une arêtes sur deux d'un chemin d'Euler, pourvu que le graphe est connexe ; des contre-exemples dans le cas non connexe sont notamment les unions disjointes de cycles impairs, ou des copies de $K_{2k+1}$.

Le problème d'Oberwolfach concerne l'existence de 2-factorisations de graphes complets en sous-graphes isomorphes. La question posée est pour quels sous-graphes cela est possible. La réponse est connue lorsque le sous-graphe est connexe, auquel cas c'est un cycle hamiltonien et ce cas particulier est le problème de la décomposition hamiltonienne, mais le cas général reste non résolu.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Graph factorization » (voir la liste des auteurs).

Bibliographie

• John Adrian Bondy et U. S. R. Murty, Graph Theory with Applications, North-Holland, 1976 (ISBN 0-444-19451-7, lire en ligne [archive du 13 avril 2010] ), chapitre ( = « Matchings ».
• Amanda G. Chetwynd et Anthony J. W. Hilton, « Regular graphs of high degree are 1-factorizable », Proceedings of the London Mathematical Society, vol. 50, n^o 2,‎ 1985, p. 193–206 (DOI 10.1112/plms/s3-50.2.193).
• Reinhard Diestel, Graph Theory, Springer, 2016-2017, 5^e éd. (ISBN 978-3-662-53621-6, lire en ligne). chapitre 2 : « Matching, covering and packing ».
• Frank Harary, Graph Theory, Addison-Wesley, 1969 (ISBN 0-201-02787-9), chapitre 9: « Factorization ».
• Thomas Niessen, « How to find overfull subgraphs in graphs with large maximum degree », Discrete Applied Mathematics, vol. 51, n^os 1–2,‎ 1994, p. 117–125 (DOI 10.1016/0166-218X(94)90101-5 ).
• Ljubomir Perkovic et Bruce Reed, « Edge coloring regular graphs of high degree », Discrete Mathematics, vol. 165–166,‎ 1997, p. 567–578 (DOI 10.1016/S0012-365X(96)00202-6 ).
• Julius Petersen, « Die Theorie der regulären Graphen », Acta Mathematica, vol. 15,‎ 1891, p. 193–220 (DOI 10.1007/BF02392606 ).
• Douglas B. West, « 1-Factorization Conjecture (1985?) », sur faculty.math.illinois.edu
• (en) Eric W. Weisstein, « Graph Factor », sur MathWorld
• (en) Eric W. Weisstein, « k-Factor », sur MathWorld
• (en) Eric W. Weisstein, « k-Factorable Graph », sur MathWorld
• Michael D. Plummer, « Graph factors and factorization: 1985–2003: A survey », Discrete Mathematics, vol. 307, n^os 7–8,‎ 2007, p. 791–821 (DOI 10.1016/j.disc.2005.11.059 ).